package 剑指offer.demo2;
//https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?

import java.util.HashMap;
import java.util.Map;

/**
 * 方法一:常规递归（效率底会有大量重复计算）
 * 方法二：迭代解
 * 方法三：升级版递归：用哈希表保存计算过程减少计算量
 * 方法四：换数组进行中间值记录和保存减少计算量
 */
public class 斐波那契数列 {
    public int Fibonacci_1(int n) {
        if (n == 1 || n == 2)
            return 1;
        else return Fibonacci_1(n - 1) + Fibonacci_1(n - 2);
    }

    public int Fibonacci_2(int n) {
        //记录初始的n == 1和n == 2时的值
        int n1 = 1;
        int n2 = 1;//n2记录的就是n=？时的值
        //n3单纯为了辅助计算用
        int n3 = 1;
        while (n > 2){
            n3 = n1;
            n1 = n2;
            n2 = n3 + n1;
            n -= 1;
        }
        return n2;
    }

    public int Fibonacci_3(int n){
        Map<Integer , Integer> map = new HashMap<>();
        if (n == 1 || n == 2){
            return 1;
        }
        //n1:n - 1;n2:n - 2
        //计算n - 1的值记录为n1
        int n1 = 0;
        if (map.containsKey(n - 1)){
            n1 = map.get(n - 1);
        }else {
            n1 = Fibonacci_3( n - 1);
            map.put(n - 1 , n1);
        }
        //计算n - 2的值记录为n2
        int n2 = 0;
        if (map.containsKey(n - 2)){
            n2 = map.get(n - 2);
        }else {
            n2 = Fibonacci_3(n - 2);
            map.put(n - 2 , n2);
        }
        return n1 + n2;
    }

    public int Fibonacci_4(int n){
        int[] arr = new int[n + 1];
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 3; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

}
